package com.xjj.tree;

import com.xjj.TreeNode;

public class M0236LowestCommonAncestorOfABinaryTree {

    TreeNode result = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 从题意上深入分析--最近父节点的条件一定是pq刚好在左右子节点中,或者本身就是qp
        // 因为再往上走,最小公共子一定是父亲的一边了

        // 通用做法可以存储所有父节点,pq都找到父节点,往上走,类似链表公共最先节点
        dfs(root, p, q);
        return result;
    }

    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }
        int val = root.val;
        int pVal = p.val;
        int qVal = q.val;

        boolean left = dfs(root.left, p, q);
        boolean right = dfs(root.right, p, q);

        boolean currentTure = val == pVal || val == qVal;
        if ((left && right) || (currentTure && (left || right))) {
            result = root;
        }

        // 本身是,或者左是,或者右是
        return currentTure || left || right;
    }
}
